\section{Podpisové schémy s určeným overovateľom}

V tejto kapitole sa budeme baviť o podpisových schémach, ktoré fungujú
tak trochu podobne ako bezznalostné dôkazy -- chceli by sme vedieť
podpísať správu špeciálne pre jedného overovateľa. Navyše, úplne
ideálne by bolo, ak by nikto iný okrem neho nebol schopný overiť náš
podpis a dokonca aby overovateľ nebol schopný dokázať niekomu inému,
že sme to podpísali my.

Pretože myšlienka určeného overovateľa (designated verifier) je veľmi
blízka bezznalostným dôkazom, budú aj definície veľmi podobné.

\begin{definicia}[Schéma s určeným overovateľom]
    Uvažujme dve komunikujúce strany -- Alicu $A$ a Boba $B$. Nech
    $P(A,B)$ je protokol pre Alicu na presvedčenie
    Boba o pravdivosti nejakého výroku $\Omega$. Môžeme hovoriť, že
    Bob je určený overovateľ, ak vie produkovať komunikácie, ktorých
    distribúcia je identická s distrubúciou komunikácii protokolu
    $P(A,B)$.
\end{definicia}

\begin{poznamka}
    Pre schémy s určeným overovateľom nemusí nutne platiť to, čo sme si
    povedali na začiatku, teda že nikto iný okrem Boba nevie overiť podpis.
    Túto vlastnosť budú mať až silné schémy s určeným overovateľom.
    V štandardnej schéme bude stačiť, že Alica dokáže Bobovi výrok
    \quoteme{Platí $\Omega$ (podpísala som správu) alebo som Bob}.
    Inak povedané, ktokoľvek iný nebude presvedčený, či správu naozaj
    podpísala Alica alebo ju nafingoval Bob.
\end{poznamka}

Niekedy ale ani táto situácia nestačí. Predstavme si Evu, ktorá sa
snaží zistiť niečo viac o podpise. Ak je presvedčená, že
\begin{enumerate}
    \item Bob sa zdá byť čestný, je nepravdepodobné, že by on
    vygeneroval falošný podpis.

    \item Ak je Eva predvedčená, že Bob ešte nevidel daný podpis, je
    tiež evidentné, že podpisovať musela Alica.
\end{enumerate}

V tomto prípade môžeme zaviesť striktnejšie predpoklady.

\begin{definicia}[Silná schéma s určeným overovateľom]
    Nech $P(A,B)$ je protokol pre Alicu a Boba na ukázanie pravdivosti
    nejakého výroku $\Omega$. Hovoríme, že $P(A,B)$ je protokol so
    silne určeným overovateľom, ak ktokoľvek vie produkovať
    komunikácie, ktoré sú nerozlíšiteľné od komunikácii protokolu
    $P(A,B)$ pre všetkých s výnikou Boba (pretože Bob musí byť schopný
    overiť pravosť podpisu). \fixme{a bob vioe generovat falosne podpisy}
\end{definicia}

\begin{poznamka}
    Z predchádzajúcej definície je evidentné, že nikto okrem Boba nesmie
    vedieť overiť pravdivosť podpisu,
    inak by vedel odlíšiť nafingovanú správu od správy od Alice.
\end{poznamka}

Samozrejme, celú túto definíciu môžeme zaviesť aj omnoho formálnejšie,
ako sme robili pri ostatných podpisových schémach.

\begin{definicia}[Designated verifier signature scheme]
    Nech $M$ je priestor všetkých možných správ (štandardne
    $M=\{0,1\}^*$). Podpisová schéma s určeným overovateľom je
    štvorica algoritmov
    $\langle Gen, Sig, Verify, Simulate \rangle$ polynomiálnych
    algoritmov kde
    \begin{itemize}
        \item $Gen(1^n)$ je pravdepodobnostný algoritmus ktorý zo
            vstupu $1^n$ vyrobí štvoricu kľúčov
            $\langle pk_A,sk_A,pk_B,sk_B \rangle$.
            Štandardne sa kľúče pre $A$ a $B$ generujú nezávisle a
            preto je možné tento algoritmus rozdeliť na dva rôzne
            algoritmy (resp. dvakrát ten istý algoritmus).

        \item $Sig(m,sk_A,pk_B)$ je pravdepodobnostný algoritmus,
            ktorý na vstupe dostane správu, privátny kľúč Alice a
            verejný kľúč Boba a na výstupe vegeneruje podpis $\sigma$
            správy $m$.

        \item $Verify(m,\sigma,sk_B,pk_A)$ je deterministický
            algoritmus, ktorý zo správy, jej podpisu, verejného kľúča
            Alice a súkromného kľúča Boba vie rozhodnúť, či bol podpis
            $\sigma$ správy $m$ podpísaný Alicou a určený pre Boba.
            Algoritmus vypíše na vstup jeden bit $b$, ktorý je 1 práve
            vtedy, ak bol podpis korektný.

        \item $Simulate(m,pk_A,sk_B)$ je pravdepodobnostný algoritmus
            produkujúci podpisy nerozlíšiteľné od podpisov algoritmu
            $Sig(m,sk_A,pk_B)$.
            V prípade, že uvažujeme silnú verziu schémy, $Simulate$ na
            vstupe nedostáva $sk_B$ ale $pk_B$.
    \end{itemize}
    Navyše, pre každú štvoricu $\langle pk_A,sk_A,pk_B,sk_B \rangle$
    vygenerovanú algoritmom $Gen(1^n)$ a pre každú správu $m\in M$
    musí platiť
    \begin{equation*}
        Verify(m, Sig(m,sk_A,pk_B),sk_B,pk_A)=1
    \end{equation*}
\end{definicia}

Formálne si teraz môžeme definovať experiment na testovanie, či naša
podpisová schéma $\Pi$ je podpisová schému s určeným overovateľom.
Budeme na to používať algoritmus
\ref{proc:ind-dv}, skrátene IND-DV, ktorý bude fungovať v roli
rozlišovateľa.

\begin{procedure}[H]
    \caption{Indistinguishable-DesignatedVerifier($D,\Pi,n$)}
    \label{proc:ind-dv}
    $\langle pk_A,sk_A,pk_B,sk_B \rangle \assign Gen_{\Pi}(1^n)$ \;
    $m \inr M$ \;
    $b \inr \{0,1\}$ \;
    \eIf{$b==0$}{$O \assign Sig_\Pi(m,sk_A,pk_B)$}
        {$O \assign Simulate_\Pi(m,pk_A,sk_B)$}
    spusť algoritmus $D$ s prístupom ku oráklu $O$. Výsledok nech je
    $b'$ \;
    \Return $b==b'$\;
\end{procedure}

Teraz môžeme hovoriť, že schéma má vlastnost určeného overovateľa, ak
pre každého polynomiálneho rozlišovateľa $D$ platí
\begin{equation*}
    Pr[IND-DV(D,\Pi,n)=1] \le \frac{1}{2} + negl(n)
\end{equation*}

Čitateľ si iste sám vie zobšeobecniť dané definície aj na silnejšiu
verziu schémy.

\subsection{Schéma od Saeednia, Kremera a Markowitcha}

Schéma je prebratá z článku \cite{designated_verifier}.
Na začiatok by sme si mohli popísať, aké spoločné parametre budú
zdieľať účastníci schémy. Bude to niečo podobné ako pri DSA podpisoch.

Uvažujme dve veľké prvočísla $p,q$ také, že $q | p-1$. 
Prvočíslo $p$ nám určuje grupu $Z_p^*$.
K tejto grupe vygenerujeme generátor $g$ jej podgrupy, ktorá má $q$
prvkov. Uvažujme ďalej hashovaciu funkciu $H$, o ktorej predpokladáme,
že je odolná voči kolíziam a s výstupom do $Z_q$.

Každý užívateľ si sám zvolí svoj súkromný kľúč $sk=x \inr Z_q$ a
zverejní svoj verejný kľúč $pk=y=g^{x} \pmod{p}$.

Potom, ako máme všetky náležitosti pripravené, Alica môže podpísať
správu určenú pre Boba nasledovne:
\begin{procedure}
    \caption{SignSKM($m$)}
    
    $k \inr Z_q$\;
    $t \inr Z_q^*$\;
    $c \assign y_B^k \mod{p}$\;
    $r \assign H(m, c)$\;
    $s \assign k \cdot t^{-1} - r \cdot x_A \mod{q}$\;
    \Return $\sigma=\langle r,s,t\rangle$\;
\end{procedure}

Ak bude teraz Bob overovať podpis, stačí mu overiť podmienku
\begin{equation*}
    H(m, (g^s y_A^r)^{t \cdot x_B} \mod{p}) == r
\end{equation*}
% (g^s y_A^r)^{t x_B} =
% g^{k x_B - r t x_A x_B + r t x_A x_B} = y_B^k

\begin{poznamka}
    Vidíme, že vďaka previazanosti Bobovho súkromného kľúča v overovacej
    rovnici by mal byť schopný overiť správu len on.
    Formálny dôkaz však nepotrebujeme (táto vlastnosť nás u obyčajnej
    schémy s určeným overovateľom netrápi) a ani autori dôkaz
    neuvádzajú.
\end{poznamka}

Aby sme ukázali, že schéma je s určeným overovateľom, musíme ukázať,
že Bob vie simulovať podpis. Simulačný algoritmus môže byť napríklad
tento:
\begin{procedure}
    \caption{SimulateSKM()}
    $r' \inr Z_q^*$\;
    $s' \inr Z_q^*$\;
    $c \assign g^{s'} y_A^{r'}$\;
    $r \assign H(m,c)$\;
    $s \assign s' r r'^{-1} \pmod{q}$\;
    $t \assign x_B r' r^{-1} \pmod{q}$\;
    \Return $\langle r,s,t \rangle$\;
\end{procedure}

\todo{co sme mali dalej, potrebujem k tomu zosit s poznamkami}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Yang, Liao}
Táto podpisová schéma patrí medzi horúce novinky, pôvodný článok
\cite{designated_verifier2}
je z Mája 2010 (ale vyskytla sa aj jeho podoba zo Septembra 2009).
Vo svojej podstate je podobná predchádzajúcej.
Máme ale pridanú hodnotu -- schéma je navrhnutá tak, 
aby bola možná extrakcia správy.
Uvažujme opäť, že Alica chce poslať Bobovi podpísanú správu.

O správe $m$ predpokladajme, že jej veľkosť je $\log_2 p - \log_2 q$
bitov.\footnote{V originálnom článku sa uvádza $m\in Z_q$,
    náš prístup je však vhodnejší pre svoju názornosť a všeobecnosť}
Toto obmedzenie na veľkosť zavádzame, pretože budeme chcieť, aby
$m||t$ sa zmestilo do $Z_p^*$ kde $t \in Z_q$.

\begin{poznamka}
    Je evidentné, že podpísaná správa nemôže byť veľmi veľká.
    Štandardne však môžeme uvažovať, že
    pokiaľ nechceme možnosť extrakcie správy, 
    môžeme podpisovať iba hash správy a nie celú správu.
    V tomto prípade ale treba dať pozor, pretože daná zmena môže
    zmeniť správnosť nasledujúcich dôkazov.
\end{poznamka}

Generácia kľčov je štandardná:
\begin{procedure}
    \caption{GenYangLiao($p,q,g$)}
    $x \inr Z_q$\;
    $y \assign g^x \pmod{p}$\;
    \Return $sk=x,\ pk=y$\;
\end{procedure}


Podpis budeme generovať nasledovne:
\begin{procedure}
    \caption{SignYangLiao()}
    $t \inr Z_q^*$\;
    $s \assign H(m||t)$\;    
    $r \assign (m||t) \cdot y_B^{x_A \cdot s} \pmod{p}$\; 
    \Return $\sigma=\langle r, s \rangle$\;
\end{procedure}

Na overovanie použijeme súkromné a verejné kľúče presne obrátene,
keďže platí $y_B^{x_A} = y_A^{x_B}$.

\begin{procedure}
    \caption{VerifyYangLiao()}
    $m'||t \assign r \cdot y_A^{-x_B\cdot s} \pmod{p}$\;
    \If{$(s \ne H(m||t))$}{
        Reject\;
    }
    Accept\;
\end{procedure}

Nato, aby sme tvrdili, že schéma je designated verifier nám treba
dokázať tieto 3 vlastnosti
\begin{enumerate}
    \item Schéma je bezpečná, teda korektný podpis pre Boba vie
        vyrobiť iba Alica.

    \item Bob vie simulovať podpisy a teda nemôže byť schopný nikoho
        presvedčiť o tom, že správu podpísala Alica.
\end{enumerate}


\begin{lema}
    Prezentovaná schéma je bezpečná.
\end{lema}
\begin{dokaz}
    \todo{}
\end{dokaz}

\begin{lema}
    Prezentovaná schéma je designed verifier schéma.
\end{lema}
\begin{dokaz}
    Ako dôkaz ukážeme, že Bob vie generovať platné podpisy na
    nerozoznanie od skutočných. Prvou časťou je simulačný algoritmus
    -- procedúra \ref{proc:simyang}
    \begin{procedure}
        \caption{SimulateYangLiao()}
        \label{proc:simyang}
        $t' \inr Z_q^*$\;
        $s' \assign H(m||t')$\;
        $r' \assign (m||t') \cdot y_A^{x_B \cdot s} \pmod{p}$\; 
        \Return $\sigma'=\langle r',s' \rangle$\;
    \end{procedure}

    Malo by byť evidentné, že simulačný algoritmus generuje iba platné
    podpisy, nakoľko $y_A^{x_B} = y_B^{x_A}$.
    Otázkou teda ostáva, či sedia aj pravdepodobnostné
    distribúcie vygenerovaných podpisov. Ak hej, tak môžeme prehlásiť,
    že schéma je designated verifier.
    Uvažujme, že
    $\overline{\sigma}=\langle \overline{r}, \overline{s} \rangle$ 
    je správa, ktorá je
    náhodne vybraná spomedzi všetkých platných podpisov.
    Uvažujme najskôr podpis $\sigma = \langle r,s \rangle$ od Alice.
    Platí
    \begin{equation*}
        Pr[\langle r,s \rangle = 
            \langle \overline{r}, \overline{s} \rangle] =
        Pr\left[ \left.
            \begin{array}{l}
            H(m||t) = \overline{s} \quad \land \\ 
            (m||t) \cdot y_B^{x_A \cdot s} = \overline{r}
            \end{array} \right| t \inr Z_q^*
        \right] = Pr[t = \overline{t} | t \inr Z_q^*] = \frac{1}{q-1}
    \end{equation*}
    Bolo by dobré vysvetliť predposlednú rovnosť, keďže nie je úplne
    transparentná. K podpisu $\overline{\sigma}$ existuje
    $\overline{t}$, podľa ktorého bol podpis zostrojený.
    Uvažujme, že $t \ne \overline{t}$. 
    Ak $H(m||t) \ne H(m||\overline{t})$, podpisy sú určite rôzne,
    pretože $s \ne \overline{s}$. Naopak, v nepravdepodobnom prípade,
    že nastane kolízia a $s = \overline{s}$, muselo by platiť
    $(m||t) \cdot y_B^{x_A \cdot s} = (m||t') \cdot y_B^{x_A \cdot s}
    \pmod{p}$, čo ale implikuje $(m||t) = (m||t') \pmod{p}$.
    Posledná rovnosť ale určite nemôže nastať, pokiaľ platí, 
    že zreťazenie $m||t$ nemá viac bitov ako číslo $p$.
    To sme ale na začiatku zakázali. Preto jediná možnosť,
    kedy sa podpisy $\sigma,\overline{\sigma}$ rovnajú je ak 
    $t=\overline{t}$.
     
    Podobne ako sme vypočítali pravdepodobnosť zhody podpisu Alice s
    náhodnou korektnou správou,
    vieme vypočítať aj pravdepodobnosť pre zhodu simulovanej
    správy s náhodnou korektnou správou a vyjde presne rovnako, $1/(q-1)$.
    Tým pádom je ale schéma perfect\footnote{Inak povedané,
        s rovnakými pravdepodobnosťami. Tak isto sme to značili aj pri
        bezznalostných dôkazoch} designated verifier.
\end{dokaz}

Autori článku tvrdia, že daná schéma je silná schéma s určeným
overovateľom. Žiaľ, dôkaz tohoto tvrdenia sa im zdal byť natoľko evidentný, 
že ho z článku vynechali a pre istotu ani nenapísali simulovanie
podpisovania iba z verejných kľúčov.

\begin{poznamka}
    Ak sa čitateľovi nepozdáva GDH problém, pretože sa mu zdá byť
    príliš silný, môže si prečítať o modifikácii Yang-Liaovej schémy,
    ktorej pri dôkaze bezpečnosti stačí obyčajný DH. Článok tiež
    obsahuje pekné zhrnutie pojmov z oblasti určeného overovateľa.
    Takže, enjoy \cite{designated_verifier_stanek}.
\end{poznamka}
